package main

import (
	"container/list"
	"math"
)

type Node struct {
	Value int
	Left  *Node
	Right *Node
}

// 暴力解
func MinHeight(root *Node) int {
	if root == nil {
		return 0
	}
	return MinHeightProcess(root)
}

func MinHeightProcess(node *Node) int {
	if node.Left == nil && node.Right == nil  {
		return 1
	}
	leftHeight, rightHeight := math.MaxInt, math.MaxInt
	if node.Left != nil {
		leftHeight = MinHeightProcess(node.Left)
	}
	if node.Right != nil {
		rightHeight = MinHeightProcess(node.Right)
	}
	return min(leftHeight, rightHeight) + 1
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// 层序遍历
func MinHeight2(root *Node) int {
	if root == nil {
		return 0
	}
	queue := list.New()
	queue.PushBack(root)
	layer := 0
	layerNum := 1
	for queue.Len() != 0 {
		layer++
		layerNum = queue.Len()
		for i:=0; i<layerNum; i++ {
			node := queue.Remove(queue.Front()).(*Node)
			if node.Left == nil && node.Right == nil {
				return layer
			}
			if node.Left != nil{
				queue.PushBack(node.Left)
			}
			if node.Right != nil{
				queue.PushBack(node.Right)
			}
		}
	}
	return layer
}


